package com.yanceysong.codetop.s81_s90;

public class S82_Easy_14_最长公共前缀 {
    /**
     * S82_Easy_14_最长公共前缀
     * <p>
     * LeetCode链接: <a href="https://leetcode.cn/problems/longest-common-prefix/">...</a>
     * <p>
     * 【题目描述】
     * 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
     * 你可以假设所有字符串仅由小写英文字母组成。
     * <p>
     * 【核心标签】字符串 / 数组 / 横向扫描 / 纵向扫描 / 分治 / Trie
     * <p>
     * 【示例】
     * 示例1: 输入: ["flower","flow","flight"] 输出: "fl"
     * 示例2: 输入: ["dog","racecar","car"] 输出: "" 解释: 不存在公共前缀
     * 示例3: 输入: ["interspecies","interstellar","interstate"] 输出: "inters"
     * 示例4: 输入: ["a"] 输出: "a"
     * 示例5: 输入: [] 输出: "" (空数组)
     * <p>
     * 【多种解法概述】
     * 1. 横向扫描（本实现）：以第一个字符串为候选前缀，依次与后续字符串求公共前缀；过程中不断缩短候选。时间 O(S)，S 为所有字符总和。
     * 2. 纵向扫描：逐列比较所有字符串同一位置字符，遇到不匹配或有字符串结束则停止。时间 O(S)。
     * 3. 分治：两两合并求公共前缀，递归分治。时间 O(S)，额外递归栈。
     * 4. Trie：构建前缀树，再沿着唯一分支向下。时间/空间都较高，适合大量查询场景。
     * 5. 二分长度：对前缀长度做二分，验证某长度是否为公共前缀。时间 O(S log L)。
     * 本题最直接、可读性最强的是横向扫描。
     * <p>
     * 【本实现思路（横向扫描）】
     * 1. 取数组第一个字符串作为当前候选前缀 candidatePrefix。
     * 2. 依次与后面每个字符串做两字符串公共前缀比较（从头匹配直到字符不同或任一结束）。
     * 3. 若某次得到的公共前缀为空，直接返回 ""（剪枝）。
     * 4. 遍历结束即得到结果。
     * <p>
     * 【复杂度分析】
     * 设字符串数量为 n，总字符数为 S。每个字符最多被比较一次（匹配失败后不再被访问）。
     * 时间复杂度: O(S)；空间复杂度: O(1)（除返回结果外）。
     * <p>
     * 【ASCII 图解（对齐展示公共前缀收缩过程）】以 ["interspecies","interstellar","interstate"] 为例：
     * 初始候选: interspecies
     * 与 "interstellar" 比较：
     * interspecies
     * interstellar
     * inters^^^^^^   （上方 inters 为公共部分，后续字符第一次不同处截断）
     * 收缩后候选: inters
     * 与 "interstate" 比较：
     * inters
     * interstate
     * inters------  （全部匹配）
     * 最终结果: inters
     * <p>
     * 【关键洞察】
     * 1. 公共前缀只会缩短，不会增长；因此逐步收缩是安全且单调的。
     * 2. 任意一个字符串为空，结果必为空；可提前剪枝。
     * 3. 若某次公共前缀变空，后续无需继续比较。
     * 4. 与纵向扫描相比，横向扫描在代码表达上更贴近“不断求交集”的语义。
     * <p>
     * 【边界与测试要点】
     * - 空数组 -> ""  \n     * - 单字符串 -> 该字符串本身  \n     * - 存在空字符串 -> ""  \n     * - 没有公共前缀 -> ""  \n     * - 全部完全相同 -> 任意即全部  \n     * - 前缀为整个最短字符串 -> 返回最短  \n     * - 大量字符串时性能：只走必要字符比较，不重复。
     */
    public String longestCommonPrefix(String[] inputArray) {
        // 边界：空引用或长度为0
        if (inputArray == null || inputArray.length == 0) {
            return "";
        }

        // 初始化候选前缀为第一个字符串
        String candidatePrefix = inputArray[0];

        int totalStrings = inputArray.length;
        // 逐个与后续字符串求公共前缀
        for (int i = 1; i < totalStrings; i++) {
            candidatePrefix = commonPrefixBetweenTwo(candidatePrefix, inputArray[i]);
            // 若已经为空，剪枝提前返回
            if (candidatePrefix.isEmpty()) {
                return "";
            }
        }
        return candidatePrefix;
    }

    /**
     * 求两个字符串的公共前缀。逐字符比较直到不同或任一结束。
     */
    private String commonPrefixBetweenTwo(String first, String second) {
        int matchLength = 0; // 已匹配前缀长度
        while (matchLength < Math.min(first.length(), second.length())
               && first.charAt(matchLength) == second.charAt(matchLength)) {
            matchLength++;
        }
        return first.substring(0, matchLength);
    }

    // ===================== 测试与演示 =====================
    public static void main(String[] args) {
        S82_Easy_14_最长公共前缀 solver = new S82_Easy_14_最长公共前缀();
        System.out.println("=== 最长公共前缀 测试开始 ===\n");

        // 测试1: 题目示例1
        testCase(solver, new String[]{"flower", "flow", "flight"}, "fl");
        // 测试2: 题目示例2 无公共前缀
        testCase(solver, new String[]{"dog", "racecar", "car"}, "");
        // 测试3: 全部相同
        testCase(solver, new String[]{"same", "same", "same"}, "same");
        // 测试4: 前缀为最短字符串
        testCase(solver, new String[]{"inter", "interview", "internet"}, "inter");
        // 测试5: 包含空字符串 -> 空
        testCase(solver, new String[]{"", "abc", "abd"}, "");
        // 测试6: 单元素
        testCase(solver, new String[]{"alone"}, "alone");
        // 测试7: 渐进缩短案例
        testCase(solver, new String[]{"interspecies", "interstellar", "interstate"}, "inters");
        // 测试8: 没有任何公共首字符
        testCase(solver, new String[]{"x", "y", "z"}, "");
        // 测试9: 边界大小写 (仅小写按题意，这里演示大小写不匹配)
        testCase(solver, new String[]{"Abc", "abc"}, "");
        // 测试10: 长度差异大
        testCase(solver, new String[]{"prefix", "pre", "prepare", "prevent"}, "pre");
        // 测试11: 大量相同前缀的数组
        testCase(solver, new String[]{"aaaaa", "aaa", "aaaaaa", "aa", "aaaa"}, "aa");
        // 测试12: 空数组
        testCase(solver, new String[]{}, "");
        // 测试13: 前缀很快变空
        testCase(solver, new String[]{"qwe", "rt", "ty"}, "");
        // 测试14: 单字符分歧
        testCase(solver, new String[]{"b", "b", "b"}, "b");
        // 测试15: 第二个字符串直接与第一个冲突
        testCase(solver, new String[]{"abc", "abd", "abf"}, "ab");

        // 额外：展示一次 ASCII 对齐演示
        asciiDemo(new String[]{"interspecies", "interstellar", "interstate"});

        System.out.println("\n=== 全部测试完成 ===");
    }

    /**
     * 单个测试用例执行并断言输出
     */
    private static void testCase(S82_Easy_14_最长公共前缀 solver, String[] input, String expected) {
        String result = solver.longestCommonPrefix(input);
        System.out.printf("输入: %s -> 输出: '%s' 期望: '%s'%n", arrayToString(input), result, expected);
        if (!result.equals(expected)) {
            throw new AssertionError("结果不匹配: got=" + result + ", expected=" + expected);
        }
    }

    /**
     * 将字符串数组格式化输出
     */
    private static String arrayToString(String[] arr) {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            sb.append('"').append(arr[i]).append('"');
            if (i < arr.length - 1) sb.append(", ");
        }
        sb.append(']');
        return sb.toString();
    }

    /**
     * ASCII 对齐演示公共前缀如何缩短
     */
    private static void asciiDemo(String[] arr) {
        System.out.println("\nASCII 公共前缀收缩过程演示:");
        if (arr == null || arr.length == 0) {
            System.out.println("(空数组)");
            return;
        }
        String candidate = arr[0];
        System.out.println("初始候选: " + candidate);
        for (int i = 1; i < arr.length; i++) {
            String next = arr[i];
            String newPrefix = commonPrefixStatic(candidate, next);
            // 打印两行对齐 + 标记公共区域
            System.out.println();
            System.out.println(candidate);
            System.out.println(next);
            // 标记公共部分，用 '^' 指示
            StringBuilder marker = new StringBuilder();
            for (int k = 0; k < newPrefix.length(); k++) marker.append('^');
            System.out.println(marker + (marker.length() > 0 ? " <- 公共前缀" : "(无公共前缀)"));
            candidate = newPrefix;
        }
        System.out.println("\n最终公共前缀: '" + candidate + "'\n");
    }

    // 静态辅助：两字符串公共前缀（供 asciiDemo 使用，避免访问实例方法）
    private static String commonPrefixStatic(String a, String b) {
        int lim = Math.min(a.length(), b.length());
        int idx = 0;
        while (idx < lim && a.charAt(idx) == b.charAt(idx)) idx++;
        return a.substring(0, idx);
    }
}
